/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-27 10:40:35
 * @LastEditors: lily
 * @LastEditTime: 2021-04-27 11:03:56
 */
/*
 * @lc app=leetcode.cn id=62 lang=javascript
 *
 * [62] 不同路径
 */

// @lc code=start
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */

//  思路：动态规划
//  dp[m][n]表示从左上走到右下的路径数量 = 到end上的路径数量+到end左边的路径数量
//  状态转移方程:  dp[m][n] = dp[m-1][n] + dp[m][n-1] 

//  复杂度：O(mn) O(mn)

//  其他解法：利用数学公式 https://leetcode-cn.com/problems/unique-paths/solution/bu-tong-lu-jing-by-leetcode-solution-hzjf/
//  复杂度：O(min(m,n)) O(1)

var uniquePaths = function (m, n) {
    let dp = Array.from(new Array(m), () => new Array(n).fill(0))
    // 设置初始值
    for (let row = 0; row < m; row++) {
        dp[row][0] = 1
    }
    for (let col = 0; col < n; col++) {
        dp[0][col] = 1
    }
    // 填表
    for (let row = 1; row < m; row++) {
        for (let col = 1; col < n; col++) {
            dp[row][col] = dp[row - 1][col] + dp[row][col - 1]
        }
    }
    return dp[m - 1][n - 1]
};
// @lc code=end

console.log(uniquePaths(3, 7));